package cn.xkai.exercise.a;

import com.google.gson.Gson;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @description: 零矩阵
 * 自己的思路：当出现0时，记录0所在位置的列索引，不退出内层循环(后面也可能出现0)，内层循环结束后直接把行数据全部填充为0，整个循环退出后，根据列索引填充列数据为0
 * 借鉴的思路：定义行、列数组，对数据为0的位置记录行、列索引为值1，再次循环判断记录数组里面行或列为1的位置填充0
 * 心得：未明确效率问题，猜测可能是set集合和int集合效率问题，因为方案里面都是进行了2次满循环
 * @author: kaixiang
 * @date: 2022-06-21
 **/
public class Solution6 {
    public void setZeroes(int[][] matrix) {
        Set<Integer> records = new HashSet<>();
        boolean fill;
        for (int i = 0; i < matrix.length; i++) {
            fill = false;
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    records.add(j);
                    fill = true;
                }
            }
            if (fill) {
                Arrays.fill(matrix[i], 0);
            }
        }
        for (Integer record : records) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][record] = 0;
            }
        }
    }

    public void setZeroesRefer(int[][] matrix) {
        int M = matrix.length;
        int N = matrix[0].length;

        int[] rowRecord = new int[M];
        int[] colRecord = new int[N];

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 0) {
                    rowRecord[i] = 1;
                    colRecord[j] = 1;
                }
            }
        }

        for (int row = 0; row < M; row++) {
            for (int col = 0; col < N; col++) {
                if (rowRecord[row] == 1 || colRecord[col] == 1) {
                    matrix[row][col] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a1 = {1, 2, 0};
        int[] a2 = {4, 5, 6};
        int[] a3 = {7, 8, 9};
        int[][] a = {a1, a2, a3};
        Solution6 solution6 = new Solution6();
        solution6.setZeroes(a);
        System.out.println(new Gson().toJson(a));
    }
}
